#include "fibonacci-heap.h"

Entry *newEntry(double elem, double priority) {
  Entry *e = (Entry *) malloc(sizeof(Entry));
  e->next = e->prev = e;
  e->priority = priority;
  e->elem = elem;
  e->degree = 0;
  e->marked = 0;
  e->child = e->parent = NULL;
  return e;
}

FibHeap *newFibHeap() {
  FibHeap *fh = (FibHeap *) malloc(sizeof(FibHeap));
  fh->size = 0;
  fh->min = NULL;
  return fh;
} 

Entry *mergeLists(Entry *one, Entry *two) {
  if (one == NULL && two == NULL)
    return NULL;
  else if (one != NULL && two == NULL)
    return one;
  else if (one == NULL && two != NULL) 
    return two;
  else {
    Entry *next = one->next;
    one->next = two->next;
    one->next->prev = one;
    two->next = next;
    two->next->prev = two;

    return one->priority < two->priority ? one : two;
  }
}

Entry *enqueue(FibHeap *fh, double value, double priority) {
  Entry *result = newEntry(value, priority);
  fh->min = mergeLists(fh->min, result);
  fh->size++;
  return result;
}

Entry *min(FibHeap *fh) {
  return fh->min;
}

int isEmpty(FibHeap *fh) {
  return fh->min == NULL;
}

int size(FibHeap *fh) {
  return fh->size;
}

FibHeap *merge(FibHeap *one, FibHeap *two) {
  FibHeap *result = newFibHeap();
  result->min = mergeLists(one->min, two->min);
  result->size = one->size + two->size;
  one->size = two->size = 0;
  one->min = NULL;
  two->min = NULL;
  return result;
}

Entry *dequeueMin(FibHeap *fh) {
  if (isEmpty(fh) )
    return NULL;
  fh->size--;
  Entry *minElem = fh->min;
  if (fh->min->next == fh->min)
    fh->min = NULL;
  else {
    fh->min->prev->next = fh->min->next;
    fh->min->next->prev = fh->min->prev;
    fh->min = fh->min->next;
  }
  if (minElem->child != NULL) {
    Entry *curr = minElem->child;
    do {
      curr->parent = NULL;
      curr = curr->next;
    } while (curr != minElem->child);
  }
  fh->min = mergeLists( fh->min, minElem->child);
  if(fh->min == NULL) return minElem;
  Entry *treeTable[1001]; int treeTableSize = 0;
  Entry *toVisit[1001]; int toVisitSize = 0;
  int i;
  for(i=0; i<1001; i++) 
    treeTable[i] = toVisit[i] = NULL;
  Entry *curr;
  for(curr = fh->min; toVisitSize == 0 || toVisit[0] != curr; curr = curr->next) {
    toVisit[ toVisitSize++ ] = curr;
  }
  for(i=0; i<toVisitSize; i++) {
    curr = toVisit[i];
    while(1) {
      while( curr->degree >= treeTableSize )
        treeTable[ treeTableSize++ ] = NULL;
      if( treeTable[ curr->degree ] == NULL ) {
        treeTable[ curr->degree ] = curr;
        break;
      }
      Entry *other = treeTable[curr->degree];
      treeTable[ curr->degree ] = NULL;
      Entry *min = (other->priority < curr->priority) ? other : curr;
      Entry *max = (other->priority < curr->priority) ? curr : other;
      max->next->prev = max->prev;
      max->prev->next = max->next;
      max->next = max->prev = max;
      min->child = mergeLists(min->child, max);
      max->parent = min;
      max->marked = 0;
      min->degree++;
      curr = min;
    }
    if (curr->priority <= fh->min->priority) fh->min = curr;
  }
  return minElem;
}

void cutNode(FibHeap *fh, Entry *e) {
  e->marked = 0;
  if(e->parent == NULL) return;
  if(e->next != e) {
    e->next->prev = e->prev;
    e->prev->next = e->next;
  }
  if(e->parent->child == e) {
    if(e->next != e) {
      e->parent->child = e->next;
    } else {
      e->parent->child = NULL;
    }
  }
  e->parent->degree--;
  e->prev = e->next = e;
  fh->min = mergeLists(fh->min, e);
  if(e->parent->marked) {
    cutNode(fh, e->parent);
  } else {
    e->parent->marked = 1;
  }
  e->parent = NULL;
}

void decreaseKeyUnchecked(FibHeap *fh, Entry *e, double priority) {
  e->priority = priority;
  if( e->parent != NULL && e->priority <= e->parent->priority) {
    cutNode(fh, e);
  }
  if( e->priority <= fh->min->priority) {
    fh->min = e;
  }
}

void decreaseKey(FibHeap *fh, Entry *e, double newPriority) {
  if(newPriority > e->priority)
    return;
  decreaseKeyUnchecked(fh, e, newPriority);
}

void delete(FibHeap *fh, Entry *e) {
  decreaseKeyUnchecked(fh, e, -214748363);
  dequeueMin(fh);
}





